/*
 * 版权所有(C)，方太互联网应用技术部，lizhixing，所有权利保留。
 * <p>
 * 项目名：	algorithm-demo
 * 文件名：	Question1448
 * 模块说明：
 * 修改历史：
 * 2025/4/16 - lizhixing - 创建。
 */
package com.lovely602.algorithm.wansuanfa;


import com.lovely602.algorithm.entity.TreeNode;

/**
 * 给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。
 * <p>
 * 示例1：请参阅文档中的示例图片：<a href="https://mmbiz.qpic.cn/sz_mmbiz_png/PGmTibd8KQBHYpf9mrSZLSUIbTH21CssPXozUEFic21SLgA6wic5eURQhPQia7ZwZtgdwtQict5BpcD2MGpSsXWwROw/640?wx_fmt=png&from=appmsg&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1">图片链接</a>
 * 输入：root = [3,1,4,3,null,1,5]
 * <p>
 * 输出：4
 * <p>
 * 解释：图中蓝色节点为好节点。
 * <p>
 * 根节点 (3) 永远是个好节点。
 * <p>
 * 节点 4 -> (3,4) 是路径中的最大值。
 * <p>
 * 节点 5 -> (3,4,5) 是路径中的最大值。
 * <p>
 * 节点 3 -> (3,1,3) 是路径中的最大值。
 * <p>
 * 示例2： 请参阅文档中的示例图片：<a href="https://mmbiz.qpic.cn/sz_mmbiz_png/PGmTibd8KQBHYpf9mrSZLSUIbTH21CssPp0pgrd5eibafiaG6g7kXWKLFPpvqFubNohiad46xz0Wc1icf4OgaonicgiaQ/640?wx_fmt=png&from=appmsg&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1">图片链接</a>
 * 输入：root = [3,3,null,4,2]
 * <p>
 * 输出：3
 * <p>
 * 解释：节点 2 -> (3, 3, 2) 不是好节点，因为 "3" 比它大。
 * <p>
 * 问题分析：我们直接使用dfs对二叉树进行遍历，需要记录从根节点到当前节点这条路径上的最大值。 如果当前节点大于等于这个最大值，说明这条路径上没有比当前节点值大的节点，所以当前节点就是好节点，最后累加好节点的个数即可。
 */
public class Question1448 {

  public int goodNodes(TreeNode root) {
    return dfs(root, Integer.MIN_VALUE);
  }

  private int dfs(TreeNode root, int maxV) {
    if (root == null)
      return 0;
    int left = dfs(root.left, Math.max(root.val, maxV));
    int right = dfs(root.right, Math.max(root.val, maxV));
    return left + right + (root.val < maxV ? 0 : 1);
  }


  public static void main(String[] args) {
    TreeNode root = new TreeNode(3);
    root.left = new TreeNode(1);
    root.right = new TreeNode(4);
    root.left.left = new TreeNode(3);
//    root.left.right = new TreeNode(1);
    root.right.left = new TreeNode(1);
    root.right.right = new TreeNode(6);
    System.out.println(new Question1448().goodNodes(root));
  }

}
